package question.solution213;

import question.SolutionTemplate;

public class Solution213 implements SolutionTemplate {

    int max = -1;

    // too slow
    public int rob(int[] nums) {
        for(int i=0;i<3 && i<nums.length;i++){
            robNext(nums, i, 0, i);
        }
        return max;
    }

    private void robNext(int[] nums, int indexToRob, int sum, int robHeadIndex){
        sum += nums[indexToRob];
        int toHeadDistance = robHeadIndex + nums.length - indexToRob;
        if(toHeadDistance < 4){
            if(sum > max){
                max = sum;
            }
            return;
        }
        if(toHeadDistance >= 4 && indexToRob + 2 < nums.length){
            robNext(nums, indexToRob + 2, sum, robHeadIndex);
        }
        if(toHeadDistance > 4 &&  indexToRob + 3 < nums.length){
            robNext(nums, indexToRob + 3, sum, robHeadIndex);
        }
    }

    public int rob2(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int[] dp1 = new int[nums.length];
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);
        if(nums.length == 2){
            return dp1[1];
        }
        for(int i=2;i<nums.length-1;i++){
            dp1[i] = Math.max(dp1[i-2] + nums[i], dp1[i-1]);
        }
        int max = dp1[nums.length-2];

        int[] dp2 = new int[nums.length];
        dp2[1] = nums[1];
        dp2[2] = Math.max(nums[1], nums[2]);
        for(int i=3;i<nums.length;i++){
            dp2[i] = Math.max(dp2[i-2] + nums[i], dp2[i-1]);
        }
        if(max < dp2[nums.length-1]){
            return dp2[nums.length-1];
        }
        return max;
    }

    public void test() {
//        int[] candidates = {10,1,2,7,6,1,5};
//        List<List<Integer>> result = combinationSum2(candidates, 8);
//        int[] candidates2 = {1};
//        List<List<Integer>> result = combinationSum2(candidates2, 1);
//        int[] nums = {1,2,3,1};
//        int[] nums = {226,174,214,16,218,48,153,131,128,17,157,142,88,43,37,157,43,221,191,68,206,23,225,82,54,118,111,46,80,49,245,63,25,194,72,80,143,55,209,18,55,122,65,66,177,101,63,201,172,130,103,225,142,46,86,185,62,138,212,192,125,77,223,188,99,228,90,25,193,211,84,239,119,234,85,83,123,120,131,203,219,10,82,35,120,180,249,106,37,169,225,54,103,55,166,124};
//        int result = rob2(nums);
        int[] nums = {0,0};
        int result = rob2(nums);
        return;
    }
}
